﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Cci;
using Microsoft.Cci.MutableCodeModel;
using Microsoft.Cci.Immutable;
using System.IO;

namespace PartialExpressionCompleter.Util
{
    static class EnumerableUtil
    {
        /// <summary>
        /// Returns a comma-separated list of the .ToString() of every value.
        /// </summary>
        public static string CommaSeparated<T>(this IEnumerable<T> xs)
        {
            return string.Join(", ", xs.Select(x => x.ToString()).ToArray());
        }
        /// <summary>
        /// Returns an IEnumerable with a single element.
        /// </summary>
        public static T[] Singleton<T>(this T x)
        {
            return new T[] { x };
        }
        /// <summary>
        /// Returns a List with a single element.
        /// </summary>
        public static List<T> SingletonList<T>(this T x)
        {
            return new List<T> { x };
        }
        /// <summary>
        /// Returns a HashSet with a single element.
        /// </summary>
        public static HashSet<T> SingletonSet<T>(this T x)
        {
            return new HashSet<T> { x };
        }
        public static bool IsEmpty<T>(this IEnumerable<T> xs)
        {
            return !xs.Any();
        }
        public static IEnumerable<T> Concat<T>(this IEnumerable<IEnumerable<T>> xss)
        {
            return (from xs in xss
                    from x in xs
                    select x);
        }
        public static IEnumerable<T> Cons<T>(this T head, IEnumerable<T> tail)
        {
            yield return head;
            foreach (var x in tail)
                yield return x;
        }
        public static bool All(this IEnumerable<bool> xs)
        {
            return xs.All(b => b);
        }

        // from http://rosettacode.org/wiki/Power_set#C.23
        public static IEnumerable<List<T>> PowerSet<T>(this IEnumerable<T> input)
        {
            var seed = new List<IEnumerable<T>>() { new List<T>() }
              as IEnumerable<List<T>>;

            return input.Aggregate(seed, (a, b) =>
              a.Concat(a.Select(x => x.Concat(new List<T>() { b }).ToList())));
        }
        public static IEnumerable<Tuple<T,U>> CartesianProduct<T,U>(
            this IEnumerable<T> left, IEnumerable<U> right)
        {
            return (from l in left
                    from r in right
                    select l.PairWith(r));
        }
        public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(
            this IEnumerable<IEnumerable<T>> left, IEnumerable<IEnumerable<T>> right)
        {
            return (from l in left
                    select (from r in right
                            select l.Concat(r)))
                   .Concat();
        }
        public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(
            this IEnumerable<IEnumerable<T>> xs, int times)
        {
            if (times == 0)
            {
                return Enumerable.Empty<T>().Singleton();
            }
            else if (times == 1)
            {
                return xs;
            }
            else
            {
                return xs.CartesianProduct(xs.CartesianProduct(times - 1));
            }
        }
        public static IEnumerable<IEnumerable<T>> CartesianProductSingletons<T>(
            this IEnumerable<T> xs, int times)
        {
            return xs.Select(x => x.Singleton()).CartesianProduct(times);
        }

        public static T ArgMin<T>(this IEnumerable<T> xs, Func<T, decimal> value)
        {
            T res = default(T);
            decimal? resVal = null;

            foreach (T x in xs)
            {
                decimal xVal = value(x);
                if (!resVal.HasValue || xVal < resVal.Value)
                {
                    res = x;
                    resVal = xVal;
                }
            }

            if (!resVal.HasValue)
            {
                throw new ArgumentException("Empty IEnumerable not allowed for ArgMin().");
            }

            return res;
        }

        public static IEnumerable<V> GetAllValues<K, V>(this Dictionary<K, V> dict,
                                                        IEnumerable<K> keys)
        {
            foreach (var key in keys)
            {
                V res;
                if(dict.TryGetValue(key, out res))
                {
                    yield return res;
                }
            }
        }
        public static HashSet<V> GetAllValuesSet<K, V>(this Dictionary<K, V> dict,
                                                       IEnumerable<K> keys)
        {
            return new HashSet<V>(dict.GetAllValues(keys));
        }

        public static List<T> WithValueSet<T>(this List<T> xs, T x, int index)
        {
            xs[index] = x;
            return xs;
        }
    }
    static class CCIUtilSuperTypes
    {
        /// <summary>
        /// Returns the supertype and all of the interfaces of the given type.
        /// </summary>
        public static IEnumerable<ITypeDefinition> GetImmediateSuperTypes(this ITypeDefinition td)
        {
            return td.BaseClasses.Concat(td.Interfaces)
                .Select(t => t.ResolvedType)
                .Where(t => !(t is Dummy));
        }

        /// <summary>
        /// Returns a flat enumeration of all of super types of a type
        /// including itself.
        /// </summary>
        /// <param name="td">Type to find super types of</param>
        /// <returns>td followed by all of its super types</returns>
        public static IEnumerable<ITypeDefinition> GetSuperTypes(this ITypeDefinition td)
        {
            return td.Cons(td.GetOnlySuperTypes());
        }
        private static Dictionary<string, List<ITypeDefinition>> superTypes =
            new Dictionary<string, List<ITypeDefinition>>();
        /// <summary>
        /// Returns a flat enumeration of all of super types of a type
        /// not including itself.
        /// </summary>
        /// <param name="td">Type to find super types of</param>
        /// <returns>all of td's super types</returns>
        public static IEnumerable<ITypeDefinition> GetOnlySuperTypes(
            this ITypeDefinition td)
        {
            string typeName = td.ToMangledString();
            List<ITypeDefinition> res;
            if (!superTypes.TryGetValue(typeName, out res))
            {
                res = td.BaseClasses
                        .Concat(td.Interfaces)
                        .SelectMany(t => GetSuperTypes(t.ResolvedType))
                        .Where(t => !(t is Dummy))
                        .Distinct(SingletonProvider<ToStringComparer<ITypeDefinition>>
                                    .Instance).ToList();
                superTypes[typeName] = res;
            }
            return res;
        }
    }
    static class CCIUtilEnum
    {
        private static readonly Dictionary<string, Dictionary<int, Query.Expression>> enumValues
            = new Dictionary<string, Dictionary<int, Query.Expression>>();
        private static Dictionary<int, Query.Expression> GetEnumValues(
                this ITypeDefinition type)
        {
            var typeName = type.ToMangledString();
            Dictionary<int, Query.Expression> res;
            if (!enumValues.TryGetValue(typeName, out res))
            {
                res = type.Fields.Where(f => f.Type.Equals(type)
                                          && f.CompileTimeValue.Value != null
                                          && f.CompileTimeValue.Value is int)
                                 .ToDictionary(f => (int) f.CompileTimeValue.Value,
                                               f => Query.ExpressionUtil.WithBaseCost(
                                                   new Query.StaticFieldLookup(f),
                                                   Query.Expression.CONSTANT_COST));
                enumValues[typeName] = res;
            }
            return res;
        }
        public static object GetEnumValue(this ITypeDefinition type, object val)
        {
            if (val is int)
            {
                var num = (int) val;
                var enumVals = type.GetEnumValues();
                if (enumVals.ContainsKey(num))
                {
                    return enumVals[num];
                }
                else
                {
                    return val;
                }
            }
            else
            {
                return val;
            }
        }
    }
    static class CCIAssemblyUtil
    {
        public static IUnit GetContainingUnit(this ITypeDefinition type)
        {
            if (type is INamespaceTypeDefinition)
            {
                return (type as INamespaceTypeDefinition).ContainingUnitNamespace.Unit;
            }
            else if (type is INestedTypeDefinition)
            {
                return (type as INestedTypeDefinition).ContainingTypeDefinition.GetContainingUnit();
            }
            else if (type is IGenericTypeInstance)
            {
                return (type as IGenericTypeInstance).GenericType.ResolvedType.GetContainingUnit();
            }
            else
            {
                return null;
            }
        }
        public static bool InSameUnitAs(this ITypeDefinition left, ITypeDefinition right)
        {
            var lunit = left.GetContainingUnit();
            var runit = right.GetContainingUnit();
            if (lunit == null || runit == null)
            {
                // If unknown, assume yes
                return true;
            }
            else
            {
                // TODO Uh, does .Equals work right here?

                var res = lunit.UnitIdentity.Equals(runit.UnitIdentity);
                if (res != (lunit.UnitIdentity.Name.ToString().Equals(runit.UnitIdentity.Name.ToString())))
                {
                }
                return res;
            }
        }
    }
    static class CCIUtil
    {
        private static readonly Dictionary<string, List<IMethodDefinition>> instMeths =
            new Dictionary<string, List<IMethodDefinition>>();
        /// <summary>
        /// Returns all instance methods of a given type, including only the
        /// most specific override for each method.
        /// </summary>
        public static IEnumerable<IMethodDefinition> GetInstanceMethods(this ITypeDefinition td)
        {
            string typeName = td.ToMangledString();
            List<IMethodDefinition> res;
            if (!instMeths.TryGetValue(typeName, out res))
            {
                res = td._GetInstanceMethods().ToList();
                instMeths[typeName] = res;
            }
            return res;
        }
        private static IEnumerable<IMethodDefinition> _GetInstanceMethods(this ITypeDefinition td)
        {
            return td.Methods.Where(m => !m.IsStatic
                    && !m.IsConstructor
                    && !m.IsStaticConstructor
                    && !m.IsSpecialName)
                .Concat((from t in td.GetOnlySuperTypes()
                         from m in GetInstanceMethods(t.ResolvedType)
                         select m))
                .Distinct(SingletonProvider<MethodComparer>.Instance);
        }
        private static readonly Dictionary<string, List<IMethodDefinition>> genInstMeths =
            new Dictionary<string, List<IMethodDefinition>>();
        /// <summary>
        /// Returns all instance methods of a given type, including only the
        /// most general override for each method.
        /// </summary>
        public static IEnumerable<IMethodDefinition> GetGeneralInstanceMethods(this ITypeDefinition td)
        {
            string typeName = td.ToMangledString();
            List<IMethodDefinition> res;
            if (!genInstMeths.TryGetValue(typeName, out res))
            {
                res = td._GetGeneralInstanceMethods().ToList();
                genInstMeths[typeName] = res;
            }
            return res;
        }
        private static IEnumerable<IMethodDefinition> _GetGeneralInstanceMethods(this ITypeDefinition td)
        {
            return (from t in td.GetOnlySuperTypes()
                         from m in GetGeneralInstanceMethods(t.ResolvedType)
                         select m)
                .Concat(td.Methods.Where(m => !m.IsStatic
                    && !m.IsConstructor
                    && !m.IsStaticConstructor))
                .Distinct(SingletonProvider<MethodComparer>.Instance);
        }

        private static readonly Dictionary<string, List<IPropertyDefinition>> properties =
            new Dictionary<string, List<IPropertyDefinition>>();
        public static IEnumerable<IPropertyDefinition> GetAllProperties(this ITypeDefinition td)
        {
            string typeName = td.ToMangledString();
            List<IPropertyDefinition> res;
            if (!properties.TryGetValue(typeName, out res))
            {
                res = td._GetAllProperties().ToList();
                properties[typeName] = res;
            }
            return res;
        }
        private static IEnumerable<IPropertyDefinition> _GetAllProperties(this ITypeDefinition td)
        {
            return td.Properties
                     .Where(p => p.Getter != null && !p.Getter.IsStatic)
                     .Concat(from t in td.GetOnlySuperTypes()
                             from p in GetAllProperties(t.ResolvedType)
                             select p)
                     .Distinct(SingletonProvider<NameComparer>.Instance
                                as IEqualityComparer<IPropertyDefinition>);
        }

        private static readonly Dictionary<string, List<IFieldDefinition>> fields =
            new Dictionary<string, List<IFieldDefinition>>();
        public static IEnumerable<IFieldDefinition> GetAllFields(this ITypeDefinition td)
        {
            string typeName = td.ToMangledString();
            List<IFieldDefinition> res;
            if (!fields.TryGetValue(typeName, out res))
            {
                res = td._GetAllFields().ToList();
                fields[typeName] = res;
            }
            return res;
        }
        private static IEnumerable<IFieldDefinition> _GetAllFields(this ITypeDefinition td)
        {
            return td.Fields.Where(f => !f.IsStatic)
                            .Concat(from t in td.GetOnlySuperTypes()
                                    from f in GetAllFields(t.ResolvedType)
                                    select f)
                   .Distinct(SingletonProvider<NameComparer>.Instance
                                as IEqualityComparer<IFieldDefinition>);
        }

        public static IArrayTypeReference CreateArrayType(this ITypeReference type, uint rank)
        {
            var res = new VectorTypeReference();
            res.ElementType = type;
            res.Rank = rank;
            return res;
        }
        public static IManagedPointerTypeReference CreateManagedPointerType(this ITypeReference type)
        {
            var t = new ManagedPointerTypeReference();
            t.TargetType = type;
            return t;
        }

        private static bool IsGenericArgsCompatible(this IGenericTypeInstanceReference leftInst,
            IGenericTypeInstanceReference rightInst, bool genericOkay)
        {
            var leftGen = leftInst.GenericType.ResolvedType;
            var rightGen = rightInst.GenericType.ResolvedType;
            var leftGenParams = leftGen.GenericParameters.ToList();
            var leftGenArgs = leftInst.GenericArguments.ToList();
            var rightGenArgs = rightInst.GenericArguments.ToList();

            if(leftGenArgs.Count != rightGenArgs.Count)
                return false;

            for(int i = 0; i < leftGenArgs.Count; i++)
            {
                var lga = leftGenArgs[i];
                if(!(genericOkay && lga is IGenericParameter))
                {
                    var lgp = leftGenParams[i] as IGenericParameter;
                    var rga = rightGenArgs[i];
                    switch(lgp.Variance)
                    {
                        case TypeParameterVariance.NonVariant:
                            if(!lga.ToString().Equals(rga.ToString()))
                                return false;
                            break;
                        case TypeParameterVariance.Covariant:
                            if(!lga.IsAssignableFrom(rga, genericOkay))
                                return false;
                            break;
                        case TypeParameterVariance.Contravariant:
                            if(!rga.IsAssignableFrom(lga, genericOkay))
                                return false;
                            break;
                    }
                }
            }
            return true;
        }

        private static Dictionary<string, bool> isComparableTo
            = new Dictionary<string,bool>();
        public static bool IsComparableTo(this ITypeDefinition left,
                                          ITypeDefinition right)
        {
            string leftStr = left.ToMangledString();
            string rightStr = right.ToMangledString();
            string key = leftStr + " ~~~ " + rightStr;
            bool res;
            if (!isComparableTo.TryGetValue(key, out res))
            {
                // Not sure on exactly when enums are comparable...
                if (leftStr.Equals("System.TypeCode")
                    || rightStr.Equals("System.TypeCode"))
                {
                    res = false;
                }
                else
                {
                    res = (leftStr.Equals(rightStr) && left.HasLessThan())
                         || ((longType.IsAssignableFrom(left) || left.IsEnum)
                             && (longType.IsAssignableFrom(right)))
                         || (longType.IsAssignableFrom(left)
                             && ((longType.IsAssignableFrom(right) || right.IsEnum)))
                         || (ulongType.IsAssignableFrom(left)
                             && (ulongType.IsAssignableFrom(right)));
                }
                isComparableTo[key] = res;
            }
            return res;
        }
        
        private static Dictionary<string, bool> isCSharpAssignableFrom
            = new Dictionary<string,bool>();
        /// <summary>
        /// Returns true if an assignment from an expression of the second type
        /// to a variable of the first type is valid.
        /// </summary>
        /// <param name="left">type of the lvalue</param>
        /// <param name="right">type of the rvalue</param>
        /// <returns>true if the rvalue can be assigned to the lvalue</returns>
        public static bool IsAssignableFrom(this ITypeDefinition left,
                                            ITypeDefinition right,
                                            bool genericOkay)
        {
            // TODO .ToString() is a workaround because generics are strange...
            string leftStr = left.ToString();
            string rightStr = right.ToString();
            if (leftStr.Equals(rightStr) || leftStr.Equals("System.Object"))
            {
                return true;
            }
            string key = leftStr + " ~~~ " + rightStr + " ~~~~ " + genericOkay;
            bool res;
            if (!isCSharpAssignableFrom.TryGetValue(key, out res))
            {
                if (!left.TypeCode.Equals(PrimitiveTypeCode.NotPrimitive)
                    && !right.TypeCode.Equals(PrimitiveTypeCode.NotPrimitive))
                {
                    switch (left.TypeCode)
                    {
                        case PrimitiveTypeCode.Int64:
                            switch (right.TypeCode)
                            {
                                case PrimitiveTypeCode.Int64:
                                case PrimitiveTypeCode.Int32:
                                case PrimitiveTypeCode.Int16:
                                case PrimitiveTypeCode.Int8:
                                case PrimitiveTypeCode.Char:
                                case PrimitiveTypeCode.UInt32:
                                case PrimitiveTypeCode.UInt16:
                                case PrimitiveTypeCode.UInt8:
                                    res = true;
                                    break;
                                default:
                                    res = false;
                                    break;
                            }
                            break;
                        case PrimitiveTypeCode.UInt64:
                            switch (right.TypeCode)
                            {
                                case PrimitiveTypeCode.Int64:
                                case PrimitiveTypeCode.Int32:
                                case PrimitiveTypeCode.Int16:
                                case PrimitiveTypeCode.Int8:
                                case PrimitiveTypeCode.Char:
                                case PrimitiveTypeCode.UInt64:
                                case PrimitiveTypeCode.UInt32:
                                case PrimitiveTypeCode.UInt16:
                                case PrimitiveTypeCode.UInt8:
                                    res = true;
                                    break;
                                default:
                                    res = false;
                                    break;
                            }
                            break;
                        case PrimitiveTypeCode.Float32:
                            switch (right.TypeCode)
                            {
                                case PrimitiveTypeCode.Int64:
                                case PrimitiveTypeCode.Int32:
                                case PrimitiveTypeCode.Int16:
                                case PrimitiveTypeCode.Int8:
                                case PrimitiveTypeCode.Char:
                                case PrimitiveTypeCode.UInt64:
                                case PrimitiveTypeCode.UInt32:
                                case PrimitiveTypeCode.UInt16:
                                case PrimitiveTypeCode.UInt8:
                                case PrimitiveTypeCode.Float32:
                                    res = true;
                                    break;
                                default:
                                    res = false;
                                    break;
                            }
                            break;
                        case PrimitiveTypeCode.Float64:
                            switch (right.TypeCode)
                            {
                                case PrimitiveTypeCode.Int64:
                                case PrimitiveTypeCode.Int32:
                                case PrimitiveTypeCode.Int16:
                                case PrimitiveTypeCode.Int8:
                                case PrimitiveTypeCode.Char:
                                case PrimitiveTypeCode.UInt64:
                                case PrimitiveTypeCode.UInt32:
                                case PrimitiveTypeCode.UInt16:
                                case PrimitiveTypeCode.UInt8:
                                case PrimitiveTypeCode.Float32:
                                case PrimitiveTypeCode.Float64:
                                    res = true;
                                    break;
                                default:
                                    res = false;
                                    break;
                            }
                            break;
                        case PrimitiveTypeCode.Int32:
                            switch (right.TypeCode)
                            {
                                case PrimitiveTypeCode.Int32:
                                case PrimitiveTypeCode.Int16:
                                case PrimitiveTypeCode.Int8:
                                case PrimitiveTypeCode.Char:
                                case PrimitiveTypeCode.UInt16:
                                case PrimitiveTypeCode.UInt8:
                                    res = true;
                                    break;
                                default:
                                    res = false;
                                    break;
                            }
                            break;
                        case PrimitiveTypeCode.UInt32:
                            switch (right.TypeCode)
                            {
                                case PrimitiveTypeCode.Int32:
                                case PrimitiveTypeCode.Int16:
                                case PrimitiveTypeCode.Int8:
                                case PrimitiveTypeCode.Char:
                                case PrimitiveTypeCode.UInt32:
                                case PrimitiveTypeCode.UInt16:
                                case PrimitiveTypeCode.UInt8:
                                    res = true;
                                    break;
                                default:
                                    res = false;
                                    break;
                            }
                            break;
                        case PrimitiveTypeCode.Int16:
                            switch (right.TypeCode)
                            {
                                case PrimitiveTypeCode.Int16:
                                case PrimitiveTypeCode.Int8:
                                case PrimitiveTypeCode.UInt8:
                                    res = true;
                                    break;
                                default:
                                    res = false;
                                    break;
                            }
                            break;
                        case PrimitiveTypeCode.UInt16:
                            switch (right.TypeCode)
                            {
                                case PrimitiveTypeCode.Int16:
                                case PrimitiveTypeCode.Int8:
                                case PrimitiveTypeCode.Char:
                                case PrimitiveTypeCode.UInt16:
                                case PrimitiveTypeCode.UInt8:
                                    res = true;
                                    break;
                                default:
                                    res = false;
                                    break;
                            }
                            break;
                        case PrimitiveTypeCode.Int8:
                            switch (right.TypeCode)
                            {
                                case PrimitiveTypeCode.Int8:
                                    res = true;
                                    break;
                                default:
                                    res = false;
                                    break;
                            }
                            break;
                        case PrimitiveTypeCode.UInt8:
                            switch (right.TypeCode)
                            {
                                case PrimitiveTypeCode.Int8:
                                case PrimitiveTypeCode.UInt8:
                                    res = true;
                                    break;
                                default:
                                    res = false;
                                    break;
                            }
                            break;
                    }
                }
                if (!res)
                {
                    // TODO needs more detail than this...
                    // TODO Does this even work? i.e. does ITypeDefinition.Equals() work right?
                    var leftInst = left.IsGeneric || left is IGenericTypeInstance
                        ? left.InstanceType : null;
                    if (leftInst is Dummy && left is IGenericTypeInstance)
                    {
                        leftInst = left as IGenericTypeInstance;
                    }
                    var rightInst = right.IsGeneric || right is IGenericTypeInstance
                        ? right.InstanceType : null;
                    if (rightInst is Dummy && right is IGenericTypeInstance)
                    {
                        rightInst = right as IGenericTypeInstance;
                    }
                    res = right.GetOnlySuperTypes()
                               .Any(sup => left.IsAssignableFrom(sup, genericOkay));
                    if (!res && leftInst != null && rightInst != null
                        && leftInst.GenericArguments.Count(a => !(a is IGenericParameter) || genericOkay) > 0
                        && rightInst.GenericArguments.Count(a => !(a is IGenericParameter)) > 0)
                    {
                        var leftGen = leftInst.GenericType.ResolvedType;
                        var rightGen = rightInst.GenericType.ResolvedType;
                        res = !(leftGen is Dummy || rightGen is Dummy)
                            && rightGen.ToString().Equals(leftGen.ToString())
                            && leftInst.IsGenericArgsCompatible(rightInst, genericOkay);
                        /*&& rightGen.GetSuperTypes()
                            .Select(t => (t is IGenericTypeInstanceReference
                                ? (t as IGenericTypeInstanceReference).GenericType
                                : t))
                            .Any(rightGenSup => leftGen.IsAssignableFrom(rightGenSup, genericOkay))*/
                    }
                    if (!res && left is IArrayType && right is IArrayType)
                    {
                        var leftArr = left as IArrayType;
                        var rightArr = right as IArrayType;
                        if (leftArr.Rank == rightArr.Rank)
                        {
                            res = leftArr.ElementType
                                         .IsAssignableFrom(rightArr.ElementType, genericOkay);
                        }
                        // TODO Better way to handle this?
                        else if (leftArr.Rank < rightArr.Rank
                            && leftArr.ElementType.Equals("System.Object"))
                        {
                            res = true;
                        }
                    }
                    if (!res && right is IArrayType && leftInst != null
                        && leftInst.GenericArguments.Count(a => !(a is IGenericParameter) || genericOkay) > 0)
                    {
                        var rightArr = right as IArrayType;
                        var arrSupTypes = rightArr.ElementType.ResolvedType
                            .GetOnlySuperTypes()
                            .Select(t => CreateArrayType(t, rightArr.Rank));
                        res = arrSupTypes.Any(ast => left.IsAssignableFrom(ast, genericOkay));
                    }
                    if (!res && left is IManagedPointerType && right is IManagedPointerType)
                    {
                        var leftPointer = left as IManagedPointerType;
                        var rightPointer = right as IManagedPointerType;
                        res = leftPointer.GetGenericParameters()
                            .UnifyUsing(new EqualToConstraint(leftPointer.TargetType,
                                                              rightPointer.TargetType)
                                        .SingletonList<Constraint>())
                            != null;
                    }
                    if (!res && genericOkay && left is IGenericParameter)
                    {
                        res = true;
                    }
                }
                if (isCSharpAssignableFrom.Count > 100000)
                    isCSharpAssignableFrom.Clear();
                isCSharpAssignableFrom[key] = res;
            }
            return res;
        }
        public static bool IsAssignableFrom(this ITypeDefinition left,
                                            ITypeDefinition right)
        {
            return left.IsAssignableFrom(right, false);
        }
        public static bool IsAssignableFrom(this ITypeReference left,
                                            ITypeReference right,
                                            bool genericOkay)
        {
            var leftDef = left.ResolvedType;
            var rightDef = right.ResolvedType;
            if (leftDef is Dummy || rightDef is Dummy)
            {
                throw new Exception("Dummy type");
            }
            else
            {
                return leftDef.IsAssignableFrom(rightDef, genericOkay);
            }
        }

        public static bool IsAssignableFromGeneric(this ITypeDefinition left, ITypeDefinition right)
        {
            return left.IsAssignableFrom(right, true);
        }

        public static ITypeReference GetGenericType(this ITypeDefinition type)
        {
            // TODO Right way?
            if (!(type is IGenericTypeInstance || type is ISpecializedNestedTypeReference)
                    && (type.GenericParameters == null || type.GenericParameters.IsEmpty()))
                return type;
            ITypeReference res;
            if (type is ISpecializedNestedTypeReference)
            {
                res = (type as ISpecializedNestedTypeReference).UnspecializedVersion;
            }
            else
            {
                res = type.InstanceType.GenericType;
                if (res is ISpecializedNestedTypeReference)
                {
                    return (res as ISpecializedNestedTypeReference).UnspecializedVersion;
                }
            }
            return res is Dummy ? (ITypeReference) type : res;
        }
        public static ITypeDefinition GetGenericErasedType(this ITypeDefinition type)
        {
            // TODO Right way?
            if (type is IGenericParameter)
            {
                return objectType;
            }
            if (!(type is IGenericTypeInstance || type is ISpecializedNestedTypeReference)
                    && (type.GenericParameters == null || type.GenericParameters.IsEmpty()))
                return type;
            INamedTypeDefinition res;
            if (type is ISpecializedNestedTypeReference)
            {
                res = (type as ISpecializedNestedTypeDefinition).UnspecializedVersion;
            }
            else
            {
                res = type.InstanceType.GenericType.ResolvedType;
            }
            if (res is Dummy)
            {
                return type;
            }
            else
            {
                return GenericTypeInstance.GetGenericTypeInstance(res,
                    Enumerable.Repeat(objectType, res.GenericParameterCount),
                    GetInternFactory());
            }
        }

        private static int DistanceFromSymmetric(this ITypeReference left, ITypeReference right)
        {
            var l = left.ResolvedType;
            var r = right.ResolvedType;
            if (l.IsAssignableFrom(r, false))
                return l.DistanceFrom(r);
            else
                return r.DistanceFrom(l);
        }

        private static Dictionary<string, int> typeDistance
            = new Dictionary<string, int>();
        private static int _DistanceFrom(this ITypeDefinition left, ITypeDefinition right)
        {
            if (!left.TypeCode.Equals(PrimitiveTypeCode.NotPrimitive))
            {
                if (!right.TypeCode.Equals(PrimitiveTypeCode.NotPrimitive)
                    || right.IsEnum)
                {
                    return 1;
                }
            }
            else if (!right.TypeCode.Equals(PrimitiveTypeCode.NotPrimitive)
                    && left.IsEnum)
            {
                return 1;
            }
            var superTypes = right.GetImmediateSuperTypes()
                      .Where(s => left.IsAssignableFrom(s))
                      .ToList();
            if (superTypes.Any())
            {
                return 1 + superTypes.Min(s => left.DistanceFrom(s));
            }
            else if ((left is IGenericTypeInstanceReference && left.InstanceType.GenericArguments.Count(a => !(a is IGenericParameter)) > 0
                || right is IGenericTypeInstanceReference && right.InstanceType.GenericArguments.Count(a => !(a is IGenericParameter)) > 0)
                && !(left.InstanceType is Dummy || right.InstanceType is Dummy))
            {
                if (left.InstanceType.GenericType.ToString()
                    .Equals(right.InstanceType.GenericType.ToString()))
                {
                    return left.InstanceType.GenericArguments.Zip(
                        right.InstanceType.GenericArguments,
                        (l, r) => l.DistanceFromSymmetric(r)).Sum();
                }
                return left.InstanceType.DistanceFrom(
                        right.InstanceType);
            }
            else if (left is IArrayType && right is IArrayType)
            {
                var leftArr = left as IArrayType;
                var rightArr = right as IArrayType;
                if (leftArr.Rank == rightArr.Rank)
                {
                    return leftArr.ElementType.DistanceFrom(rightArr.ElementType);
                }
                // TODO Better way to handle this?
                else if (leftArr.Rank < rightArr.Rank
                    && leftArr.ElementType.Equals("System.Object"))
                {
                    return 3;
                }
            }
            else if (right is IArrayType)
            {
                var rightArr = right as IArrayType;
                var superArrayTypes = rightArr.ElementType.ResolvedType.GetImmediateSuperTypes()
                    .Select(et => CreateArrayType(et, rightArr.Rank).ResolvedType)
                    .Where(s => left.IsAssignableFrom(s))
                    .ToList();
                if (superArrayTypes.Any())
                {
                    return 1 + superArrayTypes.Min(s => left.DistanceFrom(s));
                }
            }
            else if (left.ToString().Equals("System.Object"))
            {
                // Note that this is the _minimum_ distance to object.
                return 2; // TODO Object type distance.
            }
            //else
            //{
            throw new ArgumentException(left + " is not assignable from " + right);
            //}
        }

        private static int dfDepth = 0;
        /// <summary>
        /// Returns the type distance from right to left.
        /// This is undefined if left.IsAssignableFrom(right) is false.
        /// </summary>
        /// <param name="left">type of the lvalue</param>
        /// <param name="right">type of the rvalue</param>
        /// <returns>the type distance</returns>
        public static int DistanceFrom(this ITypeDefinition left, ITypeDefinition right)
        {
            // TODO .ToString() is a workaround because generics are strange...
            string leftStr = left.ToString();
            string rightStr = right.ToString();
            if (leftStr.Equals(rightStr))
            {
                return 0;
            }
            dfDepth++;
            if (dfDepth > 10)
            {
            }
            string key = leftStr + " ~~~ " + rightStr;
            int res;
            if(!typeDistance.TryGetValue(key, out res))
            {
                res = _DistanceFrom(left, right);
                typeDistance[key] = res;
            }
            dfDepth--;
            return res;
        }
        public static int DistanceFrom(this ITypeReference left, ITypeReference right)
        {
            var leftDef = left.ResolvedType;
            var rightDef = right.ResolvedType;
            if (leftDef is IGenericTypeInstanceReference && leftDef.InstanceType.GenericArguments.Count(a => !(a is IGenericParameter)) > 0
                || rightDef is IGenericTypeInstanceReference && rightDef.InstanceType.GenericArguments.Count(a => !(a is IGenericParameter)) > 0)
            {
            }
            if (leftDef is Dummy || rightDef is Dummy)
            {
                throw new Exception("Dummy type");
            }
            else
            {
                return leftDef.DistanceFrom(rightDef);
            }
        }
        public static IInternFactory GetInternFactory()
        {
            return host.InternFactory;
        }

        // Mono-recommended way to check for Mono.
        private static bool IsMicrosoftCLR()
        {
			return (Type.GetType ("Mono.Runtime") == null);
        }

        private static List<INamespaceDefinition> namespaces
            = new List<INamespaceDefinition>();
        private static int maxParamCount = 0;
        private static MetadataReaderHost host;
        public static Assembly LoadUnitFrom(string path, bool allowFail=false)
        {
            host = new PeReader.DefaultHost();
            INameTable nameTable = host.NameTable;

            
            if(IsMicrosoftCLR())
            {
                DirectoryInfo progX86Dir = new DirectoryInfo(Environment.GetFolderPath(Environment.SpecialFolder.ProgramFilesX86));
                var dotNetRefDirs = progX86Dir
                    .GetDirectories("Reference Assemblies")[0]
                    .GetDirectories("*", SearchOption.AllDirectories);
                /*
                    .GetDirectories("Microsoft")[0]
                    .GetDirectories("Framework")[0]
                    .GetDirectories(".NETFramework")[0]
                    .GetDirectories()
                    .SelectMany(d => d.GetDirectories())
                    .SelectMany(d => d.GetDirectories());                */

                DirectoryInfo winDir = new DirectoryInfo(Environment.GetFolderPath(Environment.SpecialFolder.Windows));
                DirectoryInfo sys32Dir = new DirectoryInfo(Environment.GetFolderPath(Environment.SpecialFolder.System));
                DirectoryInfo dotNetImplDir = winDir.GetDirectories("Microsoft.NET")[0];
                DirectoryInfo[] dotNetDirs = winDir.GetDirectories("v*"); // version
                foreach (DirectoryInfo dotNetDir in dotNetDirs.Concat(dotNetRefDirs).Concat(
                    new DirectoryInfo[] {
                        sys32Dir,
                        System.IO.Directory.GetParent(path)
                    }))
                {
                    host.AddLibPath(dotNetDir.FullName);
                }
            }
            else // using Mono
            {
                DirectoryInfo monoDir = new DirectoryInfo("/usr/lib/mono");
                var monoDirs = monoDir.GetDirectories("gac").Single().Cons(monoDir.GetDirectories("*.*"));
                foreach (DirectoryInfo dotNetDir in monoDirs.Concat(
                            new DirectoryInfo[] {
                            System.IO.Directory.GetParent(path)
                            })) {
                    host.AddLibPath (dotNetDir.FullName);
                }
            }

            IUnit unit;
            PdbReader pdbReader;
            try
            {
                pdbReader = new PdbReader(System.IO.File.OpenRead(System.IO.Path.ChangeExtension(path, "pdb")), host);
            }
            catch (FileNotFoundException)
            {
                pdbReader = null;
            }
            unit = host.LoadUnitFrom(path);
            if (unit is Microsoft.Cci.Dummy)
            {
                throw new Exception();
            }

            var res = Microsoft.Cci.ILToCodeModel.Decompiler
                .GetCodeModelFromMetadataModel(host, unit as IAssembly, pdbReader);

            var nsCollector = new NamespaceCollector(unit.NamespaceRoot);
            nsCollector.Traverse(res);
            namespaces = namespaces.Union(nsCollector.Namespaces)
                                   .OrderBy(ns => ns.ToString())
                                   .ToList();
            RegisterAllTypes(allowFail);
            RegisterAllStaticMethods();
            maxParamCount = (from type in GetAllTypes()
                             from meth in type.Methods
                             select meth.ParameterCount)
                            .Max();
            /*
            foreach(var t in types)
            {
                Query.MethodCache.GetMethodCacheForType(t);
            }
             */

            return res;
        }

        public static int GetMaxParameterCount()
        {
            return maxParamCount;
        }

        private static List<ITypeDefinition> types = null;
        private static ITypeDefinition booleanType, byteType, longType, ulongType, stringType;
        private static ITypeDefinition objectType = null;
        private static void RegisterAllTypes(bool allowFail=false)
        {
            SortedDictionary<string, ITypeDefinition> allTypes =
                new SortedDictionary<string, ITypeDefinition>();
            foreach (var ns in namespaces)
            {
                AddAllTypes(allTypes, ns);
            }
            types = allTypes.Values.ToList();
            try
            {
                objectType = allTypes["System.Object"];
                stringType = allTypes["System.String"];
                booleanType = allTypes["System.Boolean"];
                byteType = allTypes["System.Byte"];
                longType = allTypes["System.Int64"];
                ulongType = allTypes["System.UInt64"];
            }
            catch (KeyNotFoundException)
            {
                if (allowFail)
                {
                    return;
                }
                else
                {
                    throw;
                }
            }
        }
        private static List<IMethodDefinition> allMethods = null;
        private static List<IMethodDefinition> staticMethods = null;
        private static List<IPropertyDefinition> staticProperties = null;
        private static List<IFieldDefinition> staticFields = null;
        private static void RegisterAllStaticMethods()
        {
            allMethods = (from type in GetAllTypes()
                          where !type.ToString().Equals("System.Threading.Interlocked")
                          from meth in type.Methods
                          select meth)
                         .ToList();
            staticMethods = (from meth in allMethods
                             where meth.IsStatic && !meth.IsSpecialName
                             select meth)
                            .ToList();

            staticProperties = (from type in GetAllTypes()
                                from prop in type.Properties
                                where prop.Getter != null && prop.Getter.IsStatic
                                select prop)
                               .ToList();
            staticFields = (from type in GetAllTypes()
                            from field in type.Fields
                            where field.IsStatic
                            select field)
                           .ToList();
        }

        public static string ToMangledString(this ITypeDefinition type)
        {
            string str = type.ToString();
            if (type is INamespaceTypeDefinition)
            {
                var ntd = type as INamespaceTypeDefinition;
                if (ntd.MangleName)
                {
                    str += "`" + ntd.GenericParameterCount;
                }
            }
            return str;
        }
        private static void AddAllNestedTypes(SortedDictionary<string, ITypeDefinition> allTypes,
                                ITypeDefinition type)
        {
            foreach (var mem in type.NestedTypes)
            {
                string memStr = (mem as ITypeDefinition).ToMangledString();
                if (!allTypes.ContainsKey(memStr))
                {
                    allTypes.Add(memStr, mem as ITypeDefinition);
                }
            }
        }
        private static void AddAllTypes(SortedDictionary<string, ITypeDefinition> allTypes,
                                        INamespaceDefinition ns)
        {
            foreach (var mem in ns.Members)
            {
                if (mem is INamespaceDefinition)
                {
                    AddAllTypes(allTypes, mem as INamespaceDefinition);
                }
                else if (mem is ITypeDefinition)
                {
                    var memType = mem as ITypeDefinition;
                    string memStr = memType.ToMangledString();
                    if (!allTypes.ContainsKey(memStr))
                    {
                        allTypes.Add(memStr, memType);
                        AddAllNestedTypes(allTypes, memType);
                    }
                }
            }
        }

        public static IEnumerable<INamespaceDefinition> GetAllNamespaces()
        {
            return namespaces;
        }
        public static IEnumerable<ITypeDefinition> GetAllTypes()
        {
            return types;
        }
        public static IEnumerable<IMethodDefinition> GetAllStaticMethods()
        {
            return staticMethods;
        }
        public static IEnumerable<IMethodDefinition> GetAllMethods()
        {
            return allMethods;
        }
        public static IEnumerable<IPropertyDefinition> GetAllStaticProperties()
        {
            return staticProperties;
        }
        public static IEnumerable<IFieldDefinition> GetAllStaticFields()
        {
            return staticFields;
        }

        public static bool HasThisParameter(this IMethodReference method)
        {
            return (method.CallingConvention & CallingConvention.HasThis) != 0;
        }

        public static IEnumerable<ITypeReference> GetParameterTypes(
                this IMethodDefinition method)
        {
            if (method.HasThisParameter())
            {
                yield return method.ContainingType;
            }
            foreach (var p in method.Parameters)
            {
                if (p.IsByReference || p.IsOut)
                {
                    yield return p.Type.CreateManagedPointerType();
                }
                else
                {
                    yield return p.Type;
                }
            }
        }

        public static string ToStringNonGeneric(this ITypeReference type)
        {
            if (type is IGenericTypeInstanceReference)
            {
                var gen = type as IGenericTypeInstanceReference;
                type = gen.GenericType;
            }
            return type.ToString();
        }

        public static Boolean HasLessThan(this ITypeDefinition type)
        {
            if (!(type.TypeCode.Equals(PrimitiveTypeCode.NotPrimitive)
                || type.TypeCode.Equals(PrimitiveTypeCode.Void)
                || type.TypeCode.Equals(PrimitiveTypeCode.Boolean)
                || type.TypeCode.Equals(PrimitiveTypeCode.String)
                || type.TypeCode.Equals(PrimitiveTypeCode.Reference)))
            {
                return true;
            }
            else
            {
                return type.Methods.Any(m => m.Name.ToString().Equals("op_LessThan"));
            }
        }
        private static IEnumerable<ITypeDefinition> _GetTypesWithLessThan()
        {
            return GetAllTypes().Where(HasLessThan);
        }
        private static List<ITypeDefinition> typesWithLessThan = null;
        public static IEnumerable<ITypeDefinition> GetTypesWithLessThan()
        {
            if (typesWithLessThan == null)
                typesWithLessThan = _GetTypesWithLessThan().ToList();
            return typesWithLessThan;
        }

        private static Dictionary<string, IMethodDefinition> overrides
            = new Dictionary<string, IMethodDefinition>();
        public static IMethodDefinition GetBaseOfOverride(this IMethodDefinition method)
        {
            string methodToStr = method.ToString();
            IMethodDefinition res;
            if (!overrides.TryGetValue(methodToStr, out res))
            {
                string methodName = method.Name.ToString();
                try
                {
                    var sameNameMethods = method
                                            .ContainingType.ResolvedType
                                            .GetGeneralInstanceMethods()
                                            .Where(m => m.Name.ToString().Equals(methodName)
                                                && m.ParameterCount == method.ParameterCount);
                    if (method is IGenericMethodInstance)
                    {
                        var genArgs = (method as IGenericMethodInstance).GenericArguments;
                        if (genArgs.Any())
                        {
                            sameNameMethods = sameNameMethods.Select(
                                m => new GenericMethodInstance(m, genArgs, GetInternFactory()));
                        }
                    }
                    res = sameNameMethods
                        .First(m => SingletonProvider<MethodComparer>.Instance.Equals(m, method));
                }
                catch (InvalidOperationException)
                {
                    res = method;
                }
                overrides[methodToStr] = res;
            }
            return res;
        }
        public static bool IsOverride(this IMethodDefinition method)
        {
            return !method.GetBaseOfOverride().Equals(method);
        }

        public static string GetQualifiedName(this IMethodDefinition method)
        {
            if (method.HasThisParameter() && !method.IsConstructor)
            {
                method = method.GetBaseOfOverride();
            }
            return method.ContainingType.ToStringNonGeneric() + "." + method.Name;
        }
        public static string GetQualifiedName(this IMethodReference method)
        {
            return method.ResolvedMethod.GetQualifiedName();
        }
        public static string GetQualifiedNameWithGenArgs(this IMethodReference method)
        {
            return method.Type.ToString()
                + method.GetQualifiedName()
                + (method.GenericParameterCount > 0
                    ? "<" + method.ResolvedMethod.GenericParameters.CommaSeparated() + ">" : "");
        }
        public static bool HasSameMethodName(this IMethodReference l, IMethodReference r)
        {
            return l.Name.ToString().Equals(r.Name.ToString())                
                && l.ContainingType.ToStringNonGeneric()
                    .Equals(r.ContainingType.ToStringNonGeneric());
        }

        public static string GetMethodTypeString(this IMethodDefinition method)
        {
            return "(" + method.GetParameterTypes().CommaSeparated() + ") => " + method.Type;
        }

        public static IEnumerable<IGenericParameter> GetGenericParameters(
                this ITypeReference type)
        {
            // TODO Does this work?
            if (type is IGenericParameter)
            {
                yield return type as IGenericParameter;
            }
            else if (type is IArrayTypeReference)
            {
                var arr = type as IArrayTypeReference;
                foreach(var param in arr.ElementType.GetGenericParameters())
                {
                    yield return param;
                }
            }
            else if (type is IGenericTypeInstanceReference)
            {
                var gen = type as IGenericTypeInstanceReference;
                foreach (var param in gen.GenericArguments.SelectMany(a => a.GetGenericParameters()))
                {
                    yield return param;
                }
            }
            else if (type is IManagedPointerTypeReference)
            {
                var target = (type as IManagedPointerTypeReference).TargetType;
                foreach (var param in target.GetGenericParameters())
                {
                    yield return param;
                }
            }
        }
        public static bool ContainsGenericParameter(this ITypeReference type)
        {
            return type.GetGenericParameters().Any();
            /*
            // TODO Does this work?
            if (type is IGenericParameter)
            {
                return true;
            }
            else if (type is IArrayTypeReference)
            {
                var arr = type as IArrayTypeReference;
                return arr.ElementType.ContainsGenericParameter();
            }
            else if (type is IGenericTypeInstanceReference)
            {
                var gen = type as IGenericTypeInstanceReference;
                return gen.GenericArguments.Any(a => a.ContainsGenericParameter());
            }
            else
            {
                return false;
            }*/
        }
        public static bool ContainsGenericParameter(this ITypeReference type,
                                                    IGenericParameter param)
        {
            return type.GetGenericParameters().Contains(param);
        }

        abstract class Constraint
        {
            private readonly ITypeReference to, from;
            public Constraint(ITypeReference to, ITypeReference from)
            {
                this.to = to;
                this.from = from;
            }

            public ITypeReference To { get { return to; } }
            public ITypeReference From { get { return from; } }

            public abstract override string ToString();

            public Constraint Substitute(IGenericParameter param,
                                         ITypeReference value)
            {
                return CreateSameType(To.Substitute(param, value),
                                      From.Substitute(param, value));
            }
            public abstract Constraint CreateSameType(ITypeReference to,
                                                      ITypeReference from);
        }
        class TrivialConstraint : Constraint
        {
            public TrivialConstraint() : base(null, null) { }
            public override string ToString()
            {
                return "true";
            }
            public override Constraint CreateSameType(ITypeReference to,
                                                      ITypeReference from)
            {
                return this;
            }
        }
        class AssignableFromConstraint : Constraint
        {
            public AssignableFromConstraint(ITypeReference to, ITypeReference from)
                : base(to, from)
            { }

            public override string ToString()
            {
                return To + " is assignable from " + From;
            }

            public override Constraint CreateSameType(ITypeReference to,
                                                      ITypeReference from)
            {
                return new AssignableFromConstraint(to, from);
            }
        }
        class EqualToConstraint : Constraint
        {
            public EqualToConstraint(ITypeReference to, ITypeReference from)
                : base(to, from)
            { }

            public override string ToString()
            {
                return To + " is equal to " + From;
            }

            public override Constraint CreateSameType(ITypeReference to,
                                                      ITypeReference from)
            {
                return new EqualToConstraint(to, from);
            }
        }
        public static ITypeReference Substitute(this ITypeReference type,
            IGenericParameter param, ITypeReference value)
        {
            if (type.Equals(param))
            {
                return value;
            }
            else
            {
                if (type.ContainsGenericParameter(param))
                {
                    IEnumerable<ITypeReference> argsBase;
                    var typeDef = type.ResolvedType;
                    if (typeDef.GenericParameterCount > 0)
                    {
                        argsBase = type.ResolvedType.GenericParameters
                                                    .Cast<ITypeReference>();
                    }
                    else if(type is IGenericTypeInstanceReference)
                    {
                        var inst = type as IGenericTypeInstanceReference;
                        var genType = (type as IGenericTypeInstanceReference)
                                        .GenericType;
                        argsBase = inst.GenericArguments;
                        type = genType;
                    }
                    else
                    {
                        throw new NotImplementedException();
                    }
                    if (typeDef is INamedTypeDefinition)
                    {
                        return GenericTypeInstance.GetGenericTypeInstance(
                            typeDef as INamedTypeDefinition,
                            argsBase.Select(p => p.Equals(param) ? value : p),
                            GetInternFactory());
                    }
                    else
                    {
                        return type;
                    }
                }
                else
                {
                    return type;
                }
            }
        }
        public static IEnumerable<ITypeReference> UnifyUsing(
            this IEnumerable<IGenericParameter> genParams,
            List<ITypeReference> paramTypes, List<ITypeDefinition> argTypes)
        {
            // XXX DEBUG
            /*
            if (genParams.Count() == 1
                && paramTypes.Count == 2
                && argTypes.All(a => a != null)
                && paramTypes[0].ToString().Equals(paramTypes[1].ToString())
                && paramTypes[0].ToString().Equals("System.Collections.Generic.IEnumerable<TSource>"))
            {
            }*/
            var constraints = paramTypes.Zip(argTypes,
                (pt, at) => at == null
                            ? (Constraint)SingletonProvider<TrivialConstraint>.Instance
                            : new AssignableFromConstraint(pt, at))
               .Where(c => !(c is TrivialConstraint)
                   && !c.To.IsAssignableFrom(c.From, false))
               .ToList();

            return genParams.UnifyUsing(constraints);
        }
        private static IEnumerable<ITypeReference> UnifyUsing(
            this IEnumerable<IGenericParameter> genParams,
            List<Constraint> constraints)
        {
            List<ITypeReference> res = genParams.Cast<ITypeReference>().ToList();
            while(constraints.Count > 0)
            {
                var current = constraints[0];
                constraints.RemoveAt(0);
                var assignableWithoutGen = new LazyEval<bool>(() =>
                    current.To.IsAssignableFrom(current.From, false));
                var assignableWithGen = new LazyEval<bool>(() =>
                    current.To.IsAssignableFrom(current.From, true));
                if (current.To.ToString().Equals(current.From.ToString()))
                {
                    // Identical, do nothing.
                }
                else if (current.To is IGenericParameter)
                {
                    for (var i = 0; i < constraints.Count; i++)
                    {
                        // TODO substitute
                        constraints[i] =
                            constraints[i].Substitute(current.To as IGenericParameter,
                                                      current.From);
                        if (constraints[i].To.ToString().EndsWith("<>")
                            || constraints[i].From.ToString().EndsWith("<>"))
                        {
                        }
                    }
                    for (var i = 0; i < res.Count; i++)
                    {
                        res[i] = res[i].Substitute(current.To as IGenericParameter,
                                                                   current.From);
                    }
                }
                else if (current.To is IGenericTypeInstanceReference
                    || current.To.ResolvedType.IsGeneric)
                {
                    var genTo = current.To as IGenericTypeInstanceReference;
                    string genToTypeStr;
                    IEnumerable<ITypeReference> genToArgs;
                    if (genTo != null)
                    {
                        genToTypeStr = genTo.GenericType.ToString();
                        genToArgs = genTo.GenericArguments;
                    }
                    else
                    {
                        genToTypeStr = current.To.ToString();
                        genToArgs = current.To.ResolvedType.GenericParameters;
                    }
                    var genFrom = current.From as IGenericTypeInstanceReference;
                    if (!assignableWithGen)
                    {
                        return null;
                    }
                    else if (genFrom != null
                        && genToTypeStr.Equals(genFrom.GenericType.ToString())
                        && genToArgs.Count() == genFrom.GenericArguments.Count())
                    {
                        constraints.AddRange(genToArgs
                            .Zip(genFrom.GenericArguments,
                                (toArg, fromArg) => (Constraint)
                                    new EqualToConstraint(toArg, fromArg)));
                    }
                    else if(current is AssignableFromConstraint)
                    {
                        var fromSuperTypes = current.From.ResolvedType
                                .GetOnlySuperTypes();
                        var fromGenSuperTypes = fromSuperTypes
                                .Where(t => t is IGenericTypeInstanceReference);
                        var fromSuperMatches = fromGenSuperTypes
                                .Where(t => (t as IGenericTypeInstanceReference)
                                        .GenericType.ToString()
                                            .Equals(genToTypeStr));
                        var fromSuper = fromSuperMatches.First();
                        constraints.Add(new AssignableFromConstraint(current.To,
                                                                     fromSuper));
                    }
                    else if (current is EqualToConstraint)
                    {
                        return null;
                    }
                    else
                    {
                        throw new Exception("Unknown constraint type: " + current);
                    }
                }
                else if (current.To is IArrayTypeReference && current.From is IArrayTypeReference)
                {
                    var arrTo = current.To as IArrayTypeReference;
                    var arrFrom = current.From as IArrayTypeReference;
                    if (arrTo.Rank == arrFrom.Rank)
                    {
                        constraints.Add(current.CreateSameType(arrTo.ElementType,
                                                               arrFrom.ElementType));
                    }
                    else if (arrTo.Rank > arrFrom.Rank)
                    {
                        return null;
                    }
                    else if (arrTo.Rank < arrFrom.Rank)
                    {
                        constraints.Add(current.CreateSameType(arrTo.ElementType,
                            arrFrom.ElementType.CreateArrayType(arrFrom.Rank - arrTo.Rank)));
                    }
                }
                else if (current.To is IManagedPointerTypeReference
                    && current.From is IManagedPointerTypeReference)
                {
                    var toPointer = current.To as IManagedPointerTypeReference;
                    var fromPointer = current.From as IManagedPointerTypeReference;

                    constraints.Add(new EqualToConstraint(toPointer.TargetType,
                                                          fromPointer.TargetType));
                }
                else if (current is AssignableFromConstraint && assignableWithoutGen)
                {
                    // Do nothing.
                }
                else if (current.To.GetGenericParameters().IsEmpty()
                    || (current is EqualToConstraint && current.To is IArrayTypeReference))
                {
                    return null;
                }
                else if (current.To is IArrayTypeReference 
                    && (current.To as IArrayTypeReference).ElementType.Equals(current.From))
                {
                    return null;
                }
                else
                {
                    throw new Exception("Unable to handle constraint: " + current);
                }
            }
            return res;
        }

        public static ITypeDefinition GetType(string name)
        {
            return types.First(t => t.ToString().Equals(name));
        }
        public static ITypeDefinition GetByteType()
        {
            return byteType;
        }
        public static ITypeDefinition GetBooleanType()
        {
            return booleanType;
        }
        public static ITypeDefinition GetObjectType()
        {
            return objectType;
        }
        public static ITypeDefinition GetStringType()
        {
            return stringType;
        }
        public static IEnumerable<ITypeDefinition> GetTypesStarting(string name)
        {
            return types.Where(t => t.ToString().StartsWith(name)).ToArray();
        }
        public static IEnumerable<IMethodDefinition> GetStaticMethods(string name)
        {
            return GetAllStaticMethods()
                .Where(m => name.Equals(m.GetQualifiedName()))
                .ToList();
        }
    }
    static class CCIVisibilityUtil
    {
        public static bool IsVisibilityVisibleFrom(TypeMemberVisibility vis,
            ITypeDefinition memberTypeDef, ITypeDefinition contextType)
        {
            bool res;
            var assembly = new LazyEval<bool>(() => memberTypeDef
                        .InSameUnitAs(contextType));
            var family = new LazyEval<bool>(() => memberTypeDef.GetGenericType()
                        .IsAssignableFrom(contextType.GetGenericType(), true));
            switch (vis)
            {
                case TypeMemberVisibility.Public:
                    res = true;
                    break;
                case TypeMemberVisibility.Assembly:
                    res = assembly;
                    break;
                case TypeMemberVisibility.Private:
                    res = memberTypeDef.ToStringNonGeneric()
                        .Equals(contextType.ToStringNonGeneric());
                    break;
                case TypeMemberVisibility.Family:
                    res = family;
                    break;
                case TypeMemberVisibility.FamilyOrAssembly:
                    res = family || assembly;
                    break;
                case TypeMemberVisibility.FamilyAndAssembly:
                    res = family && assembly;
                    break;
                case TypeMemberVisibility.Other:
                    res = false;
                    break;
                default: // Assume this means protected...
                    throw new Exception("Unknown visibility: " + vis);
            }
            var nestedDef = contextType as INestedTypeDefinition;
            if (!res && nestedDef != null && nestedDef.ContainingTypeDefinition != null)
            {
                res = IsVisibilityVisibleFrom(vis, memberTypeDef,
                    nestedDef.ContainingTypeDefinition);
            }
            return res;
        }
        public static bool IsMemberVisibleFrom(
            this ITypeDefinitionMember member, ITypeDefinition contextType)
        {
            if (contextType == null)
                return true;
            ITypeDefinitionMember unspecializedVersion;
            if (member is ISpecializedMethodDefinition)
            {
                unspecializedVersion = (member as ISpecializedMethodDefinition)
                    .UnspecializedVersion;
            }
            else if (member is ISpecializedMethodReference)
            {
                unspecializedVersion = (member as ISpecializedMethodReference)
                    .UnspecializedVersion.ResolvedMethod;
            }
            else if (member is IGenericMethodInstanceReference)
            {
                unspecializedVersion = (member as IGenericMethodInstanceReference)
                    .GenericMethod.ResolvedMethod;
            }
            else if (member is ISpecializedPropertyDefinition)
            {
                unspecializedVersion = (member as ISpecializedPropertyDefinition)
                    .UnspecializedVersion;
            }
            else if (member is ISpecializedFieldDefinition)
            {
                unspecializedVersion = (member as ISpecializedFieldDefinition)
                    .UnspecializedVersion;
            }
            else
            {
                unspecializedVersion = member;
            }
            return IsVisibilityVisibleFrom(unspecializedVersion.Visibility,
                unspecializedVersion.ContainingTypeDefinition, contextType);
        }
    }
    static class GraphUtil
    {
        public static IEnumerable<int[]> EnumerateMaximumMatchings(this bool[][] graph)
        {
            int leftNodeCount = graph.Length;
            int rightNodeCount = graph[0].Length;
            List<int> edgeCount = graph.Select(l => l.Count(b => b))
                                       .ToList();
            if (edgeCount.Any(c => c == 0))
            {
                return Enumerable.Empty<int[]>();
            }

            var emptyMatching = Enumerable.Repeat<int>(-1, rightNodeCount)
                                          .ToArray();
            List<int[]> partialMatchings = emptyMatching.Singleton().ToList();
            for (int l = 0; l < leftNodeCount; l++)
            {
                List<int[]> newPartialMatchings = new List<int[]>();
                for (int r = 0; r < rightNodeCount; r++)
                {
                    var partialMatchingForR = partialMatchings.Where(m => m[r] == -1);
                    if (graph[l][r])
                    {
                        foreach (var matching in partialMatchingForR)
                        {
                            var newMatching = (int[])matching.Clone();
                            newMatching[r] = l;
                            newPartialMatchings.Add(newMatching);
                        }
                    }
                }
                partialMatchings = newPartialMatchings;
            }
            return partialMatchings;
        }
    }

    // From http://www.codeproject.com/KB/cs/genericsingleton.aspx
    public class SingletonProvider<T> where T : new()
    {
        SingletonProvider() { }

        public static T Instance
        {
            get { return SingletonCreator.instance; }
        }

        class SingletonCreator
        {
            static SingletonCreator() { }

            internal static readonly T instance = new T();
        }
    }

    /// <summary>
    /// Considers two methods equal if they have the same name
    /// and take the exact same types.
    /// </summary>
    class MethodComparer : IEqualityComparer<IMethodDefinition>
    {
        #region IEqualityComparer<IMethodDefinition> Members

        public bool Equals(IMethodDefinition x, IMethodDefinition y)
        {
            return x.Name.ToString().Equals(y.Name.ToString())
                && x.Parameters.Select(p => p.Type.ToString())
                    .SequenceEqual(y.Parameters.Select(p => p.Type.ToString()));
        }

        public int GetHashCode(IMethodDefinition m)
        {
            return m.Name.GetHashCode() ^ m.Parameters.Aggregate(0, (h, p) => h ^ p.Type.ToString().GetHashCode());
        }

        #endregion
    }

    /// <summary>
    /// Considers two ITypeDefinitionMembers equal if they have the same name.
    /// </summary>
    class NameComparer : IEqualityComparer<ITypeDefinitionMember>
    {
        #region IEqualityComparer<ITypeDefinitionMember> Members

        public bool Equals(ITypeDefinitionMember x, ITypeDefinitionMember y)
        {
            return x.Name.ToString().Equals(y.Name.ToString());
        }

        public int GetHashCode(ITypeDefinitionMember m)
        {
            return m.Name.GetHashCode();
        }

        #endregion
    }

    public class Namespace
    {
        private readonly string[] namespaces;
        private readonly string ns;
        public Namespace(string ns)
        {
            if (ns.IndexOf(']') == -1)
            {
                this.ns = ns;
            }
            else
            {
                this.ns = ns.Substring(ns.IndexOf(']') + 1);
            }
            this.namespaces = this.ns.Split('.');
        }
        protected Namespace(string[] nss)
        {
            this.namespaces = nss;
            this.ns = string.Join(".", nss);
        }
        public override string ToString()
        {
            return ns;
        }
        public override int GetHashCode()
        {
            return ns.GetHashCode();
        }
        public override bool Equals(object other)
        {
            return other is Namespace && (other as Namespace).ns.Equals(ns);
        }
        private static int CommonPrefixLength(List<Namespace> nss)
        {
            if (nss.Count == 0)
                return 0;
            else if (nss.Count == 1)
                return nss[0].namespaces.Length;
            int minLen = nss.Min(ns => ns.namespaces.Length);
            for (int i = 0; i < minLen; i++)
            {
                if (!nss.Skip(1).All(ns => ns.namespaces[i].Equals(nss[0].namespaces[i])))
                {
                    return i;
                }
            }
            return minLen;
        }
        public int CommonPrefixLength(Namespace other)
        {
            int minLen = Math.Min(namespaces.Length, other.namespaces.Length);
            for (int i = 0; i < minLen; i++)
            {
                if (!namespaces[i].Equals(other.namespaces[i]))
                {
                    return i;
                }
            }
            return minLen;
        }
        public static Namespace CommonPrefix(IEnumerable<Namespace> nssin)
        {
            if (nssin.IsEmpty())
            {
                return NamespaceUtil.emptyNamespace;
            }
            var nss = nssin
                .Where(ns => !ns.Equals(NamespaceUtil.primitiveNamespace))
                .ToList();
            if (nss.IsEmpty())
            {
                return NamespaceUtil.primitiveNamespace;
            }
            return new Namespace(nss[0].namespaces
                .Take(CommonPrefixLength(nss))
                .ToArray());
        }
        public Namespace CommonPrefix(Namespace other)
        {
            if (this.IsPrimitive)
                return other;
            else if (other.IsPrimitive)
                return this;
            else
                return new Namespace(namespaces
                    .Take(CommonPrefixLength(other))
                    .ToArray());
        }
        public bool IsPrimitive
        {
            get { return this.Equals(NamespaceUtil.primitiveNamespace); }
        }
        public int Length
        {
            get { return namespaces.Length; }
        }
    }
    public static class NamespaceUtil
    {
        internal static readonly Namespace emptyNamespace = new Namespace("");
        internal static readonly Namespace primitiveNamespace = new Namespace("PRIMITIVE");
        public static Namespace GetNamespace(this ITypeDefinition type)
        {
            if (type != null && !(type is Dummy))
            {
                if (type.TypeCode.Equals(TypeCode.Object))
                {
                    string typeName = type.ToString();
                    if (typeName.Contains('.'))
                    {
                        string namespaceName = typeName.Substring(0, typeName.LastIndexOf('.'));
                        return new Namespace(namespaceName);
                    }
                }
                return primitiveNamespace;
            }
            throw new ArgumentNullException();
        }
        public static Namespace GetNamespace(this ITypeReference type)
        {
            return type.ResolvedType.GetNamespace();
        }
        public static Namespace CommonPrefix(this IEnumerable<Namespace> xs)
        {
            return Namespace.CommonPrefix(xs);
        }
    }

    public class ComparerOn<K, C> : IComparer<K>, IEqualityComparer<K>
    {
        private Func<K, C> compareOn;
        public ComparerOn(Func<K, C> compareOn)
        {
            this.compareOn = compareOn;
        }
        public int GetHashCode(K obj)
        {
            return compareOn(obj).GetHashCode();
        }
        public bool Equals(K x, K y)
        {
            try
            {
                return compareOn(x).Equals(compareOn(y));
            }
            catch (NullReferenceException)
            {
                return false;
            }
        }
        public int Compare(K x, K y)
        {
            return (compareOn(x) as IComparable<C>).CompareTo(compareOn(y));
        }
    }
    public class ToStringComparer<T> : ComparerOn<T, string>
    {
        public ToStringComparer() : base(obj => obj.ToString()) { }
    }
    public struct LazyEval<T>
    {
        private Func<T> lazy;
        private T value;
        public LazyEval(Func<T> lazy)
        {
            if (lazy == null)
                throw new ArgumentNullException();
            this.lazy = lazy;
            this.value = default(T);
        }
        public T Value
        {
            get
            {
                if (lazy != null)
                {
                    value = lazy();
                    lazy = null;
                }
                return value;
            }
        }
        public static implicit operator T(LazyEval<T> le)
        {
            return le.Value;
        }
    }

    public static class TupleUtil
    {
        public static Tuple<T, U> PairWith<T, U>(this T first, U second)
        {
            return new Tuple<T, U>(first, second);
        }
    }
    /*
    // from http://stackoverflow.com/questions/955982/tuples-or-arrays-as-dictionary-keys-in-c/956043#956043
    public struct Tuple<T, U> : IEquatable<Tuple<T, U>>
    {
        readonly T first;
        readonly U second;

        public Tuple(T first, U second)
        {
            this.first = first;
            this.second = second;
        }

        public T First { get { return first; } }
        public U Second { get { return second; } }

        public override int GetHashCode()
        {
            //return first.GetHashCode() ^ second.GetHashCode();
            return 0;
        }

        public override bool Equals(object obj)
        {
            if (obj == null || GetType() != obj.GetType())
            {
                return false;
            }
            return Equals((Tuple<T, U>)obj);
        }

        public bool Equals(Tuple<T, U> other)
        {
            return ((other.first != null && other.first.Equals(first))
                    || (other.first == null && first == null))
                && ((other.second != null && other.second.Equals(second))
                    || (other.second == null && second == null));
        }

        public override string ToString()
        {
            return "(" + First + ", " + Second + ")";
        }
    }*/

    // Workaround for the fact the LINQ results are not considered equal even if their result sets are equal.
    public class TupEqualityComparer<T, U> : IEqualityComparer<Tuple<IEnumerable<T>, IEnumerable<U>>>
    {
        public bool Equals(Tuple<IEnumerable<T>, IEnumerable<U>> x, Tuple<IEnumerable<T>, IEnumerable<U>> y)
        {
            return x.Item1.SequenceEqual(y.Item1) && x.Item2.SequenceEqual(y.Item2);
        }
        public int GetHashCode(Tuple<IEnumerable<T>, IEnumerable<U>> x)
        {
            return x.Item1.Aggregate(0, (acc, val) => acc ^ val.GetHashCode())
                ^ x.Item2.Aggregate(0, (acc, val) => acc ^ val.GetHashCode());
        }
    }

    public static class HashUtil
    {
        public static string ToHexString(this byte[] xs)
        {
            return string.Join("", xs.Select(x => x.ToString("x2")).ToArray());
        }
    }
}
